#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include "euler/prime_table.hpp"
#include "euler.h"

BEGIN_PROBLEM(347, solve_problem_347)
	PROBLEM_TITLE("Largest integer divisible by two primes")
	PROBLEM_ANSWER("11109800204052")
	PROBLEM_DIFFICULTY(1)
	PROBLEM_FUN_LEVEL(1)
	PROBLEM_TIME_COMPLEXITY("")
	PROBLEM_SPACE_COMPLEXITY("")
END_PROBLEM()

static int M(int p, int q, int N, const std::vector<int> &p_powers)
{
	int m = 0;
	for (long long qq = q; qq <= N / p; qq *= q)
	{
		int pp = *std::lower_bound(p_powers.crbegin(), p_powers.crend(), N/qq, std::greater<int>());
		if (pp * qq > m)
			m = (int)(pp * qq);
	}
	return m;
}

static void solve_problem_347()
{
#if 0
	const int N = 100;
#else
	const int N = 10000000;
#endif

	// Find out all possible prime factors.
	euler::prime_table<int> ptable(N/2);
	std::vector<int> primes(ptable.begin(), ptable.end());
	int np = (int)primes.size();

	// For each prime p, create a list of each power of p not exceeding N.
	std::vector<std::vector<int>> pp(np);
	for (int i = 0; i < np; i++)
	{
		int p = primes[i];
		for (long long t = 1; t <= N; t *= p)
			pp[i].push_back((int)t);
	}

	// Enumerate each pair of (p, q) and sum up M(p, q, N).
	long long S = 0;
	for (int i = 0; i < np; i++)
	{
		int p = primes[i];
		if ((long long)p * p >= N)
			break;

		for (int j = i + 1; j < np; j++)
		{
			int q = primes[j];
			if (p * q > N)
				break;

			int m = M(p, q, N, pp[i]);
			//std::cout << "M(" << p << ", " << q << ", " << N << ") = " << m << std::endl;
			S += m; // S += M(p, q, N, pp[i]);
		}
	}
	std::cout << S << std::endl;
}
